1. Technical Field
The present invention relates to an ALM tree constructing apparatus effectively utilizing, when a stream is distributed via the ALM tree, a remaining bandwidth found after the construction of the ALM tree, and an ALM tree constructing method.
2. Background Art
One of typical stream distribution techniques utilizes an ALM tree. FIGS. 12 and 13 outline such an ALM tree. As shown in FIG. 12, terminals 11, 12, 13, 14, 15, 16 and 17 are connected to a star communication network 10, such as the Internet and a Local Area Network (LAN).
Here consider, for example, the case where the terminal 11 tries to distribute a data stream directly to all the other terminals 12 to 17; this causes the data stream amount to exceed the upper limit of the bandwidth of a line connected to the terminal 11, resulting in delay in the data stream distribution.
Thus as shown in FIG. 13, a logically hierarchical structure is constructed to have the terminal 11; namely the distribution source of the data stream, allocated as the topmost node (root node). In other words, the terminal 11 distributes the received data stream only to the terminals 12 and 13. Each of the terminals 12 and 13 reproduces the data stream received from the terminal 11 as well as distributes the data stream to the terminals 14 and 15, and 16 and 17 which are lower in the level. The above construction makes possible dispersing the traffic, which contributes to delay-free stream distribution.
Here, when video is distributed via the ALM tree on the Internet, the following major indicators are used to evaluate the quality of the video to be distributed: (i) the resolution of the video to be distributed (the bit rate of the distributed video) and (ii) the degree of delay developed when the video is distributed from the distribution source (hereinafter referred to as “source”) to each receiver (For an interactive application such as a distance lecture, for example, both of a higher resolution and a shorter delay are important).
Since two or more user terminals (hereinafter simply referred to as “terminals” or “nodes”) form an ALM tree, the construction of the ALM tree is significantly affected by (i) the upper limit and the lower limit of bandwidths for an upload link and a download link of a node, and (ii) a delay time between the terminals.
In a typical internet use (receiving content), more data is uploaded than downloaded. Thus most of upper limits of bandwidths for download links (hereinafter referred to as “downlink”) are set higher than those for upload links (hereinafter referred to as “uplink”).
For example, the Asymmetric Digital Subscriber Line (ADSL) subscribed by a lot of users has uplink a bandwidth as small as just over 10% of its downlink bandwidth. Accordingly, the construction of the ALM tree depends on the upper limit of the uplink bandwidth of a node and the delay between the nodes.
A lot of techniques have been proposed to construct various ALM trees taking the two metrics into consideration. For example, Non Patent Literature 1 offers an algorithm for constructing an ALM tree: when an uplink bandwidth of a node and a delay between nodes are provided as an input, (i) the maximum delay of the ALM tree does not exceed the given upper limit, and (ii) the bandwidth of the ALM tree available for the distribution is the greatest.